{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Closest Marked Node"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph #array #shortest-path #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图 #数组 #最短路 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumDistance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到最近的标记节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个正整数 <code>n</code> ，表示一个 <strong>索引从 0 开始的有向加权</strong> 图的节点数量，以及一个 <strong>索引从 0 开始的二维数组</strong> <code>edges</code> ，其中 <code>edges[i] = [u<sub>i</sub>, v<sub>i</sub>, w<sub>i</sub>]</code> 表示从节点 <code>u<sub>i</sub></code> 到节点 <code>v<sub>i</sub></code> 的一条权重为 <code>w<sub>i</sub></code> 的边。</p>\n",
    "\n",
    "<p>并给定一个节点 <code>s</code> 和一个节点数组 <code>marked</code> ；你的任务是找到从 <code>s</code> 到 <code>marked</code> 中 <strong>任何</strong> 节点的 <strong>最短</strong> 距离。</p>\n",
    "\n",
    "<p>返回一个整数，表示从 <code>s</code> 到 <code>marked</code> 中任何节点的最短距离，如果从 s 到任何标记节点没有路径，则返回 <code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>示例 1：</b></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 4, edges = [[0,1,1],[1,2,3],[2,3,2],[0,3,4]], s = 0, marked = [2,3]\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>从节点 0（绿色节点）到节点 2（红色节点）有一条路径，即 0-&gt;1-&gt;2，距离为 1 + 3 = 4。 \n",
    "从节点 0 到节点 3（红色节点）有两条路径，即 0-&gt;1-&gt;2-&gt;3 和 0-&gt;3，分别距离为 1 + 3 + 2 = 6 和 4。 \n",
    "它们中的最小值是 4。\n",
    "</pre>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/06/13/image_2023-06-13_16-34-38.png\" style=\"width: 185px; height: 180px;\" /></p>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 5, edges = [[0,1,2],[0,2,4],[1,3,1],[2,3,3],[3,4,2]], s = 1, marked = [0,4]\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>从节点 1（绿色节点）到节点 0（红色节点）没有路径。 \n",
    "从节点 1 到节点 4（红色节点）有一条路径，即 1-&gt;3-&gt;4，距离为 1 + 2 = 3。 \n",
    "因此答案是 3。\n",
    "</pre>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/06/13/image_2023-06-13_16-35-13.png\" style=\"width: 300px; height: 285px;\" /></p>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 4, edges = [[0,1,1],[1,2,3],[2,3,2]], s = 3, marked = [0,1]\n",
    "<b>输出：</b>-1\n",
    "<b>解释：</b>从节点 3（绿色节点）到任何一个标记节点（红色节点）都没有路径，因此答案是 -1。\n",
    "</pre>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/06/13/image_2023-06-13_16-35-47.png\" style=\"width: 420px; height: 80px;\" /></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>提示：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 500</code></li>\n",
    "\t<li><code>1 &lt;= edges.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>edges[i].length = 3</code></li>\n",
    "\t<li><code>0 &lt;= edges[i][0], edges[i][1] &lt;= n - 1</code></li>\n",
    "\t<li><code>1 &lt;= edges[i][2] &lt;=&nbsp;10<sup>6</sup></code></li>\n",
    "\t<li><code>1 &lt;= marked.length&nbsp;&lt;= n - 1</code></li>\n",
    "\t<li><code>0 &lt;= s, marked[i]&nbsp;&lt;= n - 1</code></li>\n",
    "\t<li><code>s != marked[i]</code></li>\n",
    "\t<li>如果&nbsp;<code>i != j</code>&nbsp;则&nbsp;<code>marked[i] != marked[j]</code></li>\n",
    "\t<li>图中可能有 <strong>重复的边 。</strong></li>\n",
    "\t<li>图的生成不会出现 <strong>自环</strong> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-closest-marked-node](https://leetcode.cn/problems/find-the-closest-marked-node/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-closest-marked-node](https://leetcode.cn/problems/find-the-closest-marked-node/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4\\n[[0,1,1],[1,2,3],[2,3,2],[0,3,4]]\\n0\\n[2,3]', '5\\n[[0,1,2],[0,2,4],[1,3,1],[2,3,3],[3,4,2]]\\n1\\n[0,4]', '4\\n[[0,1,1],[1,2,3],[2,3,2]]\\n3\\n[0,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def minimumDistance(self, n: int, edges: List[List[int]], s: int, marked: List[int]) -> int:    \n",
    "        table = {}\n",
    "        inf = 999999999\n",
    "        for e in edges:\n",
    "            table.setdefault(e[0],{})\n",
    "            table[e[0]].setdefault(e[1],inf)\n",
    "            table[e[0]][e[1]] = min(table[e[0]][e[1]], e[2])\n",
    "        d = [inf for _ in range(n)]\n",
    "        d[s] = 0\n",
    "        heap = [(0,s)]\n",
    "        marked = set(marked)\n",
    "        visited = [False for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            if not heap:\n",
    "                return -1\n",
    "            now = heapq.heappop(heap)\n",
    "            while heap and visited[now[1]]:\n",
    "                try:\n",
    "                    now = heapq.heappop(heap)\n",
    "                except:\n",
    "                    return -1\n",
    "            if now[1] in marked:\n",
    "                return d[now[1]]\n",
    "            visited[now[1]] = True\n",
    "            if now[1] in table:\n",
    "                for y in table[now[1]]:\n",
    "                    dis = d[now[1]] + table[now[1]][y]\n",
    "                    if dis < d[y]:\n",
    "                        d[y] = dis\n",
    "                        heapq.heappush(heap, (d[y],y))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def minimumDistance(self, n: int, edges: List[List[int]], s: int, marked: List[int]) -> int:    \n",
    "        table = {}\n",
    "        inf = 999999999\n",
    "        for e in edges:\n",
    "            table.setdefault(e[0],{})\n",
    "            table[e[0]].setdefault(e[1],inf)\n",
    "            table[e[0]][e[1]] = min(table[e[0]][e[1]], e[2])\n",
    "        d = [inf for _ in range(n)]\n",
    "        d[s] = 0\n",
    "        heap = [(0,s)]\n",
    "        marked = set(marked)\n",
    "        visited = [False for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            if not heap:\n",
    "                return -1\n",
    "            now = heapq.heappop(heap)\n",
    "            while heap and visited[now[1]]:\n",
    "                try:\n",
    "                    now = heapq.heappop(heap)\n",
    "                except:\n",
    "                    return -1\n",
    "            x = now[1]\n",
    "            if x in marked:\n",
    "                return d[x]\n",
    "            visited[x] = True\n",
    "            if x in table:\n",
    "                for y in table[x]:\n",
    "                    dis = d[x] + table[x][y]\n",
    "                    if dis < d[y]:\n",
    "                        d[y] = dis\n",
    "                        heapq.heappush(heap, (d[y],y))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def minimumDistance(self, n: int, edges: List[List[int]], s: int, marked: List[int]) -> int:    \n",
    "        table = {}\n",
    "        inf = 999999999\n",
    "        for e in edges:\n",
    "            table.setdefault(e[0],{})\n",
    "            table[e[0]].setdefault(e[1],inf)\n",
    "            table[e[0]][e[1]] = min(table[e[0]][e[1]], e[2])\n",
    "        d = [inf for _ in range(n)]\n",
    "        d[s] = 0\n",
    "        heap = [(0,s)]\n",
    "        marked = set(marked)\n",
    "        visited = [False for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            if not heap:\n",
    "                return -1\n",
    "            now = heapq.heappop(heap)\n",
    "            while heap and visited[now[1]]:\n",
    "                try:\n",
    "                    now = heapq.heappop(heap)\n",
    "                except:\n",
    "                    return -1\n",
    "            if now[1] in marked:\n",
    "                return d[now[1]]\n",
    "            visited[now[1]] = True\n",
    "            if now[1] in table:\n",
    "                for y in table[now[1]]:\n",
    "                    dis = d[now[1]] + table[now[1]][y]\n",
    "                    if dis < d[y]:\n",
    "                        d[y] = dis\n",
    "                        heapq.heappush(heap, (d[y],y))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, n: int, edges: List[List[int]], s: int, marked: List[int]) -> int:\n",
    "        pq, visited, g, marked = [(0, s)], set(), defaultdict(list), set(marked)\n",
    "        for u, v, w in edges:\n",
    "            g[u].append((v, w))\n",
    "        \n",
    "        while pq:\n",
    "            cost, node = heappop(pq)\n",
    "            if node not in visited:\n",
    "                visited.add(node)\n",
    "                if node in marked:\n",
    "                    return cost\n",
    "                for nei, c in g[node]:\n",
    "                    heappush(pq, (cost + c, nei))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, n: int, edges: List[List[int]], s: int, marked: List[int]) -> int:\n",
    "        d,m,h,heap=defaultdict(list),set(marked),set(),[(0,s)]\n",
    "        for i,j,k in edges:\n",
    "            d[i].append((j,k))\n",
    "        while heap:\n",
    "            i,j=heappop(heap)\n",
    "            if j not in h:\n",
    "                if j in m:\n",
    "                    return i\n",
    "                h.add(j)\n",
    "                for a,b in d[j]:\n",
    "                    if a not in h:\n",
    "                        heappush(heap,(i+b,a))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, n: int, edges: List[List[int]], s: int, marked: List[int]) -> int:\n",
    "        f=[float('inf')]*n\n",
    "        g=defaultdict(list)\n",
    "        for x,y,w in edges:\n",
    "            g[x].append((y,w))\n",
    "        q=[]\n",
    "        heappush(q,(0,s))\n",
    "        while q:\n",
    "            t,x =heappop(q)\n",
    "            if f[x]<t:continue\n",
    "            for y,w in g[x]:\n",
    "                if f[y]>t+w:\n",
    "                    f[y]=t+w\n",
    "                    heappush(q,(t+w,y))\n",
    "        res=float('inf')\n",
    "        for i in marked:\n",
    "            if f[i]==-1:continue\n",
    "            res=min(res,f[i])\n",
    "        if res == float('inf'):return -1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minimumDistance(self, n: int, edges: List[List[int]], s: int, marked: List[int]) -> int:\n",
    "        graph, marked, visited, heap = defaultdict(list), set(marked), set(), [[0, s]]\n",
    "        for i, j, k in edges:\n",
    "            graph[i].append([j, k])\n",
    "\n",
    "        while heap:\n",
    "            a, b = heapq.heappop(heap)\n",
    "            if b not in visited:\n",
    "                if b in marked:\n",
    "                    return a\n",
    "\n",
    "                visited.add(b)\n",
    "                for j, k in graph[b]:\n",
    "                    if j not in visited:\n",
    "                        heapq.heappush(heap, [a+k, j])\n",
    "\n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, n: int, edges: List[List[int]], s: int, marked: List[int]) -> int:\n",
    "        dc, marked, has, heap = defaultdict(list), set(marked), set(), [[0,s]]\n",
    "        for i,j,k in edges: dc[i].append([j,k])\n",
    "        while heap:\n",
    "            a, b = heapq.heappop(heap)\n",
    "            if b not in has:\n",
    "                if b in marked: return a\n",
    "                has.add(b)\n",
    "                for j,k in dc[b]:\n",
    "                    if j not in has: heapq.heappush(heap, [a+k,j])\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, n: int, edges: List[List[int]], s: int, marked: List[int]) -> int:\n",
    "        dc, marked, has, heap = defaultdict(list), set(marked), set(), [[0,s]]\n",
    "        for i,j,k in edges: dc[i].append([j,k])\n",
    "        while heap:\n",
    "            a, b = heapq.heappop(heap)\n",
    "            if b not in has:\n",
    "                if b in marked: return a\n",
    "                has.add(b)\n",
    "                for j,k in dc[b]:\n",
    "                    if j not in has: heapq.heappush(heap, [a+k,j])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, n: int, edges: List[List[int]], s: int, marked: List[int]) -> int:\n",
    "        g = defaultdict(set)\n",
    "        for u,v,w in edges:\n",
    "            g[u].add((v,w))\n",
    "        dist = [float('inf')]*n\n",
    "        dist[s] = 0\n",
    "        mheap = [(0, s)]\n",
    "        while mheap:\n",
    "            dis,x = heapq.heappop(mheap)\n",
    "            if dist[x]<dis:\n",
    "                continue\n",
    "            for nextN,nextD in g[x]:\n",
    "                if dis+nextD < dist[nextN]:\n",
    "                    dist[nextN] = dis+nextD\n",
    "                    mheap.append((dist[nextN], nextN))\n",
    "\n",
    "        min_dis = float('inf')\n",
    "        for t in marked:\n",
    "            min_dis = min(min_dis, dist[t])\n",
    "        return min_dis if min_dis<float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, n: int, edges: List[List[int]], s: int, marked: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        \n",
    "        :param n: \n",
    "        :param edges: \n",
    "        :param s: \n",
    "        :param marked: \n",
    "        :return: \n",
    "        \"\"\"\n",
    "        m1 = defaultdict(list)\n",
    "        for i in edges:\n",
    "            m1[i[0]].append((i[1], i[2]))\n",
    "        sd1 = SortedList(key=lambda x:x[1])\n",
    "        sd1.add((s, 0))\n",
    "        mkset = set(marked)\n",
    "        used = {}\n",
    "        while sd1:\n",
    "            first, st = sd1.pop(0)\n",
    "            if first in mkset:\n",
    "                return st\n",
    "            if first in used:\n",
    "                if used[first] <= st:\n",
    "                    continue\n",
    "            used[first] = st\n",
    "            for i in m1.get(first, []):\n",
    "                sd1.add((i[0], i[1]+st))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, n: int, edges: List[List[int]], s: int, marked: List[int]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b, w in edges:\n",
    "            g[a].append([b, w])\n",
    "        dis = [inf] * n \n",
    "        h = [[0, s]]\n",
    "        while h:\n",
    "            d, node = heappop(h)\n",
    "            if dis[node] <= d:\n",
    "                continue\n",
    "            dis[node] = d \n",
    "            for nxt, delta in g[node]:\n",
    "                if delta + dis[node] < dis[nxt]:\n",
    "                    heappush(h, [delta + dis[node], nxt])\n",
    "        ans = min(dis[mark] for mark in marked)\n",
    "        return ans if ans != inf else -1 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, n: int, edges: List[List[int]], s: int, marked: List[int]) -> int:\n",
    "        f=[-1]*n\n",
    "        g=defaultdict(list)\n",
    "        for x,y,w in edges:\n",
    "            g[x].append((y,w))\n",
    "        q=[]\n",
    "        heappush(q,(0,s))\n",
    "        while q:\n",
    "            t,x =heappop(q)\n",
    "            if f[x]!=-1:continue\n",
    "            f[x]=t\n",
    "            for y,w in g[x]:\n",
    "                heappush(q,(t+w,y))\n",
    "        res=10**18\n",
    "        for i in marked:\n",
    "            if f[i]==-1:continue\n",
    "            res=min(res,f[i])\n",
    "        if res ==10**18:return -1\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
